package com.cet.algorithm.栈与队列;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 滑动窗口最大值
 * @author: 陈恩涛
 * @create: 2022-07-12 15:36
 **/
public class LC239 {

    public static void main(String[] args) {
//        final int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        final int[] nums = {7,6,5,4,3,2,1};


        for (int i : maxSlidingWindow(nums, 3)) {
            System.out.println(i);
        }

    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();

        // 初始滑窗元素入队列
        for (int i = 0; i < k; ++i) {
            // 如果队尾元素比加入的元素小，则移除
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        // 队首元素为最大值
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // 窗口右移中，首位的下标已经不在窗口中，则移除
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }

}
